关键词: 软容量约束带随机需求, 近似算法, 近似比

Abstract: In this paper, we consider the facility location problem with soft capacities and stochastic demands. In this problem, given the facility set and client set, each client has a stochastic demand, and each facility has a capacity but can be open more than once. The opening cost of each facility is fixed, and the connection cost between each client and facility is also given. The objective is to open some facilities and connect each client to an open facility whose capacity can not be exceeded such that the total cost is minimized. For the facility location problem with soft capacities and stochastic demands, we design an approximation algorithm. First, we construct the corresponding uncapacitated facility location problem with stochastic demands for each capacity case. Second, We solve the uncapacitated facility location problem with stochastic demands and obtain a feasible solution. Third, we construct a feasible solution to the original problem. Finally, we analyze the running time of the algorithm. We prove that the approximation factor for the algorithm is 6.

Key words: soft capacities and stochastic demands, approximation algorithm, approximation factor